package com.yvon.service.demo.algorithm.offer;

/**
 * @author : Yvon
 * @since : 2022-07-21
 */
public class P13 {

    public static void main(String[] args) {

    }

    class Solution {
        private boolean[][] mark;
        private int m;
        private int n;
        private int k;

        public int movingCount(int m, int n, int k) {
            this.mark = new boolean[m][n];
            this.m = m;
            this.n = n;
            this.k = k;
            return dfs(0, 0);
        }
        private int dfs(int i, int j) {
            if (i >= m || j >= n || mark[i][j] || (i%10 +i/10 + j%10 + j/10) > k) {
                return 0;
            }
            mark[i][j] = true;
            return 1 + dfs(i + 1, j ) + dfs(i, j + 1);
        }
    }
}
